package algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序：归并排序是有2步骤，一个步骤是分，把数组1分2, 2分4,4分8，一直分到子数组只有一个元素为止；
 * 然后又开始合并，每次比较2个子数组，用临时数组来存放比较后的排序好的合并数组，
 * 再把临时数据拷贝回原数组，所以不是原地排序
 */
public class MergeSortTest {
    public static void main(String[] args) {
        int[] arr = { 1, 12, 2, 13, 3, 14, 4, 15, 5, 16, 17, 17, 177, 18, 8, 8, 19 };
        sort(arr);
        System.out.println("result arr = " + Arrays.toString(arr));
    }

    public static void sort(int[] arr){
        mergeSort(arr, 0, arr.length - 1);
    }

    public static void merge(int[] arr, int begin, int mid, int end){
        int[] temp = new int[end - begin + 1];

        int first = begin;
        int second = mid + 1;
        int index = 0;
        while(first <= mid && second <= end){
            if(arr[first] < arr[second]){
                temp[index++] = arr[first++];
            }else{
                temp[index++] = arr[second++];
            }
        }
        // 上面比较大小的过程可能会有某个子数组还有剩余元素没有遍历到
        while(first <= mid){
            temp[index++] = arr[first++];
        }

        while(second <= end){
            temp[index++] = arr[second++];
        }

        int k = 0;
        for(int i = begin; i <= end; i++){
            arr[i] = temp[k++];
        }
    }

    public static void mergeSort(int[] arr, int begin, int end){
        if(begin >= end) return;

        int mid = (begin + end)/2;

        mergeSort(arr, begin, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, begin, mid, end);
    }
}
